#include "main/utils.h"
using namespace std;

bool isValid(string str) {
  return !str.empty() &&
         stoi(str) <= 255 &&
         (str.size() == 1 || str[0] != '0');
}

void restoreIPCore(const string& str,
                   int index,
                   vector<string> tmp_str,
                   vector<string>& results) {
  if (index == str.size() && tmp_str.size() == 4) {
    string result;
    int i = 0;
    for (i = 0; i < tmp_str.size() - 1; ++i) {
      result += (tmp_str[i] + ".");
    }
    result += tmp_str[i];
    results.push_back(result);
    return;
  }
  for (int i = index; i < str.size(); ++i) {
    if (isValid(str.substr(index, i - index + 1)) && tmp_str.size() < 4) {
      tmp_str.push_back(str.substr(index, i - index + 1));
      restoreIPCore(str, i + 1, tmp_str, results);
      tmp_str.pop_back();
    }
  }
}

vector<string> restoreIP(const string& str) {
  vector<string> results;
  vector<string> tmp_str;
  restoreIPCore(str, 0, tmp_str, results);
  return results;
}

int main() {
  string str = "10203040";
  auto ret = restoreIP(str);
  for (auto ip : ret) {
    cout << ip << endl;
  }

  return 0;
}
